class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if (needle == NULL || haystack == NULL) {
			return NULL;
		}
		if (*needle == 0) {
			return haystack;
		}

		int n = strlen(haystack);
		int m = strlen(needle);
		vector<int> next(m);

		next[0] = 0;
		for (int i = 1; i < m; ++i) {
			int k = next[i - 1];
			while (k > 0 && needle[k] != needle[i]) {
				k = next[k - 1];
			}
			if (needle[k] == needle[i]) {
				next[i] = k + 1;
			} else {
				next[i] = 0;
			}
		}

		int cur = 0;
		for (int i = 0; i < n; ++i) {
			while (cur > 0 && needle[cur] != haystack[i]) {
				cur = next[cur - 1];
			}
			if (needle[cur] == haystack[i]) {
				++cur;
			}
			if (cur == m) {
				return haystack + i - cur + 1;
			}
		}
		return NULL;

    }
};